A random number generator (RNG) is an algorithm or circuit operable to generate a sequence of numbers or symbols that bear no discernable relationship to one another, i.e., appear random. RNGs have many significant uses, including gaming, statistical analysis, simulation and, perhaps most crucially, cryptography. While algorithmic pseudo-random number generators (“PRNG”s) are capable of generating difficult-to-predict numbers, memory limitations force their output eventually to repeat. This compromises and renders them of limited use for particularly demanding applications.
Assuming “true” random numbers exist, natural (i.e., physical) processes, as opposed to man-made algorithms, provide the most likely source for true random numbers. Many natural processes yield numbers that defy current prediction techniques, but almost all are prohibitively expensive to implement in hardware (e.g., an integrated circuit (IC) that can be readily employed in a computer) or otherwise unsuitable (e.g., cannot generate true random numbers at a suitable rate).
One natural process, however, has proven to be a useful basis for a true random number generator (“TRNG”), and that is electronic noise, particularly evidencing itself as phase noise (or “jitter”) in a ring oscillator (RO). As those skilled in the pertinent art are familiar, an RO is constructed by series-coupling an odd number of signal inverting gates (e.g., inverters) in a loop. An input state of one of the inverting gates is then toggled, causing a cascading state change in each subsequent inverting gate that resonates around the RO at a frequency that is largely a function of the time constants of the inverting gates. ROs are commonly used as a source of clock signals and therefore engineered for frequency stability using various known techniques for attenuating jitter. However, if jitter is left unchecked, ROs become sources of randomness, or “entropy,” and thus capable of serving as the heart of a TRNG. Various conventional techniques have been developed to take advantage of the jitter an RO can exhibit.